package q322_coinChange;

import java.util.Arrays;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int coin : coins) { // 遍历所有我们能用的硬币
            for (int j = coin; j <= amount; j++) { // 遍历我们dp的容量 完全背包是采用正序遍历的
                //
                if (dp[j - coin] != Integer.MAX_VALUE) {

                    dp[j] = Math.min(dp[j], dp[j - coin] + 1); // 当前的dp[j] = 当前的dp[j] + 当前的dp[j - nums[i]]
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
